package leetcode_动态规划;

import java.util.Arrays;

/**
 * 机器人可以获得的最大金币数
 * 算法: 网格图 dp
 * 多一个约束, 多一个参数
 *
 * @author yezh
 * @date 2025/1/12 21:35
 */
public class _3418 {

    public int maximumAmount(int[][] coins) {
        int m = coins.length, n = coins[0].length;
        int[][][] dp = new int[m + 1][n + 1][3];
        for (int[] row : dp[0]) Arrays.fill(row, Integer.MIN_VALUE);
        for (int i = 1; i <= m; i++) {
            Arrays.fill(dp[i][0], Integer.MIN_VALUE);
            for (int j = 1; j <= n; j++) {
                int coin = coins[i - 1][j - 1];
                if (i == 1 && j == 1) {
                    dp[1][1][0] = coin;
                    dp[1][1][1] = dp[1][1][2] = Math.max(coin, 0);
                    continue;
                }
                int x = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]);
                int y = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]);
                int z = Math.max(dp[i - 1][j][2], dp[i][j - 1][2]);
                // 之前都选, 现在也选
                dp[i][j][0] = x + coin;
                // 之前都选, 现在不选; 之前不选一次, 现在选
                dp[i][j][1] = Math.max(x, y + coin);
                // 之前不选一次, 现在不选; 之前不选两次, 现在必须选
                dp[i][j][2] = Math.max(y, z + coin);
            }
        }
        return Math.max(dp[m][n][0], Math.max(dp[m][n][1], dp[m][n][2]));
        // for (int[][] mat : dp)
        //     for (int[] row : mat)
        //         Arrays.fill(row, Integer.MIN_VALUE);
        // return dfs(0, 0, dp coins, 2);
    }

    int dfs(int i, int j, int[][][] mem, int[][] coins, int k) {
        if (i >= coins.length || j >= coins[0].length)
            return Integer.MIN_VALUE;
        int coin = coins[i][j];
        if (i == coins.length - 1 && j == coins[0].length - 1)
            return k > 0 ? Math.max(coin, 0) : coin;
        if (mem[i][j][k] != Integer.MIN_VALUE)
            return mem[i][j][k];
        // 选
        int res = Math.max(dfs(i + 1, j, mem, coins, k), dfs(i, j + 1, mem, coins, k)) + coin;
        // 不选
        if (coin < 0 && k > 0)
            res = Math.max(res, Math.max(dfs(i + 1, j, mem, coins, k - 1), dfs(i, j + 1, mem, coins, k - 1)));
        return mem[i][j][k] = res;
    }

}
